A query optimizer is a component of a database management system that attempts to determine the most efficient way to execute a query. The optimizer considers the possible query plans for a given query and attempts to determine which of those plans will be the most efficient. Cost-based query optimizers assign an estimated “cost” to each possible query plan and select the plan with the smallest cost. Costs are used to estimate the runtime cost of evaluating the query, in terms of the number of I/O operations required, the CPU requirements, and other factors determined from the database.
Systems using histograms for cost-based query optimization suffer from efficiency problems when using a higher resolution and are error-prone when using a lower resolution. What is needed is a reliable cost estimation without the efficiency and error penalties associated with histograms.